/*
https://leetcode.cn/problems/rMeRt2/solution/z-by-endlesscheng-6ver/
 */
import java.util.HashMap;
import java.util.Map;

public class SolutionLCP69 {

    static Map<Character,int[]> map=new HashMap<>();
    static int full=2012;
    static int INF=Integer.MAX_VALUE/2;

    static {
        map.put('e',new int[]{0,4,7});
        map.put('l',new int[]{3,3,3});
        map.put('o',new int[]{5,2,3});
        map.put('h',new int[]{7,1,1});
        map.put('t',new int[]{8,1,1});
        map.put('c',new int[]{9,1,1});
        map.put('d',new int[]{10,1,1});
    }

    public int Leetcode(String[] words) {
        Map<Integer,Integer>[] maps=new Map[words.length];
        for (int i=0;i<words.length;i++){
            maps[i]=new HashMap<>();
            dfs1(words[i],0,0,maps[i]);
        }
        int[][] dp=new int[words.length][1<<11];
        for (int i = 0; i < words.length; i++) {
            for (int i1 = 0; i1 < 1 << 11; i1++) {
                dp[i][i1]=-1;
            }
        }
        int ans=dfs2(0,0,dp,maps);
        return ans==INF?-1:ans;
    }

    public void dfs1(String s,int state,int num,Map<Integer,Integer> xMap){
        if (!xMap.containsKey(state) || xMap.get(state)>num){
            xMap.put(state,num);
        }
        for (int i=0;i<s.length();i++){
            if (map.containsKey(s.charAt(i))){
                int[] t=map.get(s.charAt(i));
                int n=(state>>t[0])&t[2];
                if (n<t[1]){
                    String cs=s.substring(0,i).concat(s.substring(i+1));
                    dfs1(cs,state+(1<<t[0]),num+i*(s.length()-i-1),xMap);
                }
            }
        }
    }

    public int merge(int a,int b){
        for (Map.Entry<Character, int[]> entry : map.entrySet()) {
            int[] t=entry.getValue();
            int c1=(a>>t[0])&t[2];
            int c2=(b>>t[0])&t[2];
            if (c1+c2>t[1]){
                return -1;
            }
            a+=c2<<t[0];
        }
        return a;
    }

    public int dfs2(int k,int state,int[][] dp,Map<Integer,Integer>[] maps){
        if (k==dp.length){
            return state==full?0:INF;
        }
        if (dp[k][state]!=-1){
            return dp[k][state];
        }
        int ans=Math.min(INF,dfs2(k+1,state,dp,maps));
        for (Map.Entry<Integer, Integer> entry : maps[k].entrySet()) {
            int n=merge(state,entry.getKey());
            if (n>0){
                ans=Math.min(ans,entry.getValue()+dfs2(k+1,n,dp,maps));
            }
        }
        dp[k][state]=ans;
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new SolutionLCP69().Leetcode(new String[]{"xrlyorvy","zjobucvp","sckadde","lllettpw","ee","ecotcws","jeahbqki"}));
    }
}
